#pragma once

struct Node
{
	char _val;
	Node* _left;
	Node* _right;
	Node(int x = int())
		: _val(x)
		, _left(nullptr)
		, _right(nullptr)
	{

	}
};

class BTree
{
	Node* _root = nullptr;

	void _BTCreat(Node* root , vector<char>& arr, int& pi)
	{
		if (pi >= arr.size()) return ;
		if (_root == nullptr)
		{
			root = new Node(arr[(pi++)]);
			_root = root;
		}
		if (pi < arr.size()) 
			root->_left = new Node(arr[pi++]);
		if (pi < arr.size()) 
			root->_right = new Node(arr[pi++]);
		_BTCreat(root->_left, arr, pi);
		_BTCreat(root->_right, arr, pi);

		return ;
	}
	void PrevOrder(Node* root)
	{
		if (root == nullptr) return;

		cout << root->_val << " ";
		PrevOrder(root->_left);
		PrevOrder(root->_right);
	}
	void InOrder(Node* root)
	{
		if (root == nullptr) return;

		InOrder(root->_left);
		cout << root->_val << " ";
		InOrder(root->_right);
	}
	void PostOrder(Node* root)
	{
		if (root == nullptr) return;

		PostOrder(root->_left);
		PostOrder(root->_right);
		cout << root->_val << " ";
	}
public:
	void BTCreat(vector<char>& arr, int& pi)
	{
		_BTCreat(_root, arr, pi);
	}

	void PrevOrder()
	{
		PrevOrder(_root);
		cout << endl;
	}
	void InOrder()
	{
		InOrder(_root);
		cout << endl;
	}
	void PostOrder()
	{
		PostOrder(_root);
		cout << endl;
	}
};
